package leetcode_core.leetcode_1;

import org.junit.Test;

import java.util.Arrays;

public class Rob1 {
    private int[] memo;
    public int rob(int[] nums) {
        memo = new int[nums.length+5];
        Arrays.fill(memo,-1);
        return dp(nums,0);//从0开始走过
    }

    /**
     * dp函数的定义:表示对于一个数组nums,从start开始走,能够抢劫得到的最大金额是多少?
     * @param nums
     * @param start
     * @return
     */
    private int dp(int[] nums,int start){
        //start代表的是索引,表示目前的状态,当start大于等于nums.length了,这时候不可能在抢劫了,是空区间,返回0值
        if(start >= nums.length){//由于可能存在+2的情况,因此这里写>=
            return 0;
        }
        //备忘录优化
        if(memo[start] != -1){
            return memo[start];
        }
        //择优,取max
        int res = Math.max(
                dp(nums,start+2)+nums[start],//选择抢这个屋子的
                dp(nums,start+1)//选择不抢这个屋子的
        );
        memo[start] = res;
        return res;
    }

    @Test
    public void testCaseOne(){
        System.out.println(rob(new int[]{1, 2, 3,1}));
    }
    @Test
    public void testCaseTwo(){
        System.out.println(rob(new int[]{2,7,9,3,1}));
    }

}
